【LeetCode 63】Unique Paths II 不同路径II

发表于 | 分类于


“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.”
Linux的哲学就是“在危险面前放声大笑”，呵呵，不是这句，应该是“一切靠自己，自力更生”才对。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 */
public class leetcode63 {
    public static int uniquePathsWithObstacles (int[][] obstacleGrid) {
        if (obstacleGrid.length <= 0)
            return 0;
        if (obstacleGrid[0][0] == 1)
            return 0;
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i == 0 || j == 0)
                    dp[i][j] = dp[i > 0 ? i - 1 : 0][j > 0 ? j - 1 : 0];
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[n - 1][m - 1];
    }

    //O(m)空间复杂度

    /**
     *要注意的是因为有可能存在障碍物，所以i或j为0时不再是总为1了
     */
    public static int uniquePathWithObstacles2 (int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[] dp = new int[m];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];
            for (int j = 1; j < m; j++) {
                if (obstacleGrid[i][j] != 1)
                    dp[j] += dp[j - 1];
                else
                    dp[j] = 0;
            }
        }
        return dp[m - 1];
    }

    public static void main (String []args) {
        leetcode63.uniquePathWithObstacles2(new int [][]{{0},{0}});
    }
}
Thanks!